#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "Tree.h"

/***************************************************************************************************************/
/**********************************    struct Node & struct Tree    ********************************************/
/***************************************************************************************************************/
typedef struct Node_t
{
    struct Node_t*  m_smaller;
    struct Node_t*  m_bigger;
    struct Node_t*  m_parent;
    void*           m_data;
}Node;

struct Tree_t
{
    Node*   m_root    ;               /*  Pointer to root                                         */
    Node*   m_begin   ;               /*  Pointer to the smallest node                            */
    Node    m_end     ;               /*  Stab node for end. Its parent is the biggest in tree    */
    int (*m_less)(void* , void* );    /*  less function forcomparing 2 datas                      */
};

/*******************************************************************************************************************/
/*****************************    Forward Decleration of internal Functions    *************************************/
/*******************************************************************************************************************/
static Node* NodeCreate(void* _data);

/*  Function for removal. Get the node to free and update is parent to get on the apropriate side replacing node.  */
static void UpdateParentAndFreeNode(Node* _node, Node* _replNode);

/*  Function to find the next node.                                                                                */
static Node* NodeNext(Node* _node);

/*  Function to find the prev node.                                                                                */
static Node* NodePrev(Node* _node);

/*  Recursive function for deleting nodes.                                                                         */
static void DeleteNodes(Node* _node, Node* _endNode);

/*  Recursive function for finding the equal node. If not found return 0                                           */
static Node* NodeFind(Tree* _tree, Node* _node, void* _data);
/*******************************************************************************************************************/
/*******************************************    Internal Functions    **********************************************/
/*******************************************************************************************************************/
static Node* NodeCreate(void* _data)
{
    Node* node = (Node*)malloc(sizeof(Node));
    if(!node)
    {
        fprintf(stderr, "error on allocating\n");
        return 0;
    }

    node->m_data    = _data;
    node->m_smaller = 0;
    node->m_bigger  = 0;

    return node;
}


static void UpdateParentAndFreeNode(Node* _node, Node* _replNode)
{
    if(_node->m_parent->m_smaller == _node)
    {
        _node->m_parent->m_smaller = _replNode;
    }
    else
    {
        _node->m_parent->m_bigger = _replNode;
    }

    free(_node);
}


static Node* NodeFind(Tree* _tree, Node* _node, void* _data)
{
    if(!_node)      /*  Node not found*/
    {
        return 0;
    }
    if(_tree->m_less(_data, _node->m_data))
    {
        _node = _node->m_smaller;
        return NodeFind(_tree, _node, _data);
    }
    else if(_tree->m_less(_node->m_data, _data))
    {
        _node = _node->m_bigger;
        return NodeFind(_tree, _node, _data);
    }

    return _node;   /*  Node found  */
}


static Node* NodeNext(Node* _node)
{
    assert(_node);
    assert(_node->m_data != (void*)0xdeadbeef);       /*  not stab end                                    */

    if(_node->m_bigger)                               /*  If there is a bigger child                      */
    {
        _node = _node->m_bigger;
        while(_node->m_smaller)                       /*  Go to the smallest in the bigger side == next   */
        {
            _node = _node->m_smaller;
        }
        return _node;
    }
    /*  Else go to the parent is bigger => the branch is in his smaller branch  */
    while(_node->m_parent->m_smaller != _node)
    {
        _node = _node->m_parent;
    }

    return _node->m_parent;
}


static Node* NodePrev(Node* _node)
{
    assert(_node);

    if(_node->m_smaller)              /*  If there is a smaller child                     */
    {
        _node = _node->m_smaller;
        while(_node->m_bigger)        /*  Go to the biggest in the smaller side == prev   */
        {
            _node = _node->m_bigger;
        }
        return _node;
    }
    /*  Else go to the parent is smaller => the branch is in his bigger branch  */
    while(_node->m_parent->m_bigger != _node)
    {
        _node = _node->m_parent;
    }

    return _node->m_parent;
}


static void DeleteNodes(Node* _node, Node* _endNode)
{
    if(_node->m_smaller)
    {
        DeleteNodes(_node->m_smaller, _endNode);
    }

    if(_node->m_bigger && _node->m_bigger != _endNode)
    {
        DeleteNodes(_node->m_bigger, _endNode);
    }

    free(_node);
}

/*******************************************************************************************************************/
/*******************************************    Interface Functions    *********************************************/
/*******************************************************************************************************************/

Tree* TreeNew(int(*_less)(void*, void*))
{
    Tree* tree = 0;

    assert(_less);

    tree = (Tree*)malloc(sizeof(Tree));
    if(!tree)
    {
        fprintf(stderr, "error in Tree Allocation\n");
        return 0;
    }

    tree->m_less  = _less;
    tree->m_begin = &(tree->m_end);
    tree->m_root  = 0;

    tree->m_end.m_smaller = 0                ;
    tree->m_end.m_bigger  = 0                ;
    tree->m_end.m_parent  = 0                ;
    tree->m_end.m_data    = (void*)0xdeadbeef;

    return tree;
}


TreeIter TreeFind(Tree* _tree, void* _data)
{
    Node*       node   = 0;

    assert(_tree);

    node = NodeFind(_tree, _tree->m_root, _data);
    if(!node)                               /*  Check the node we got. If it 0 return the stab end     */
    {
        return (TreeIter)( &(_tree->m_end) );
    }

    return (TreeIter)node;
}


TreeIter TreeInsert(Tree* _tree, void* _data)
{
    Node*       node      = 0;
    Node*       newNode   = 0;

    assert(_tree);

    newNode = NodeCreate(_data);
    if(!newNode)                                     /*  If allocation failed, return end stab          */
    {
        return (TreeIter)&(_tree->m_end);
    }

    if(!_tree->m_root)                                /*  If there isn't root, init all parameters        */
    {
        _tree->m_root  = newNode;
        newNode->m_parent = 0;
        newNode->m_bigger = &(_tree->m_end);

        _tree->m_begin = _tree->m_root;
        _tree->m_end.m_parent = _tree->m_root;

        return (TreeIter)_tree->m_root;
    }

    node = _tree->m_root;
    while(1)
    {
        if(_tree->m_less(_data, node->m_data))          /*  The data is smaller                             */
        {
            if(!node->m_smaller)                        /*  If there isn't smaller child. insert there      */
            {
                node->m_smaller = newNode;
                if(node == _tree->m_begin)
                {
                    _tree->m_begin = node->m_smaller;   /*  Update begin with new smallest                  */
                }
                break;
            }
            node = node->m_smaller;                     /*  Go forhead to smaller                           */
        }
        else                                            /*  The data is bigger or equal                     */
        {
            /*  If there isn't biggeer child, and not the stab end. Insert in there                         */
            if(!node->m_bigger || node->m_bigger == &(_tree->m_end) )
            {
                node->m_bigger = newNode;
                if(node == _tree->m_end.m_parent)
                {
                    _tree->m_end.m_parent = node->m_bigger;
                    node->m_bigger->m_bigger = &(_tree->m_end);             /*  Update end.parent with new biggest      */
                }
                break;
            }
            node = node->m_bigger;                                          /*  Go forhead to bigger                    */
        }
    }

    newNode->m_parent = node;                                           /*  Update the parent parameter of new node         */

    return (TreeIter)newNode;
}


void* TreeGetData(TreeIter _iter)
{
    assert(_iter);
    assert(((Node*)_iter)->m_data != (Node*)0xdeadbeef);      /*  not stab end */

    return ((Node*)_iter)->m_data;
}


int TreeIsEmpty(Tree* _tree)
{
    assert(_tree);

    return (_tree->m_root == 0);
}


TreeIter TreeBegin(Tree* _tree)
{
    assert(_tree);

    return (TreeIter)_tree->m_begin;
}


TreeIter TreeEnd(Tree* _tree)
{
    assert(_tree);

    return (TreeIter)( &(_tree->m_end) );
}


int TreeIsEqual(TreeIter _iter1, TreeIter _iter2)
{
    assert(_iter1 && _iter2);

    return (Node*)_iter1 == (Node*)_iter2;
}


TreeIter TreeNext(TreeIter _iter)
{
    return (TreeIter)NodeNext((Node*)_iter);
}


TreeIter TreePrev(TreeIter _iter)
{
    return (TreeIter)NodePrev((Node*)_iter);
}


void TreeDel(Tree* _tree)
{
    assert(_tree);

    if(_tree->m_root)                                 /*  If the root exist => walk on tree to delete */
    {
        DeleteNodes(_tree->m_root, &_tree->m_end);
    }

    free(_tree);
}

/*  There are 3 situations of removing:
    1. There aren't childs to node. To remove there is only need to update parent's branch(smaller or bigger), and free node.
    2. There are 2 childs to node. To remove we find the next node and copy his data on removal node. If next has bigger node
       then attach it to the next parent. else free the next node.
    3. There is 1 child. To remove we attach the parent of removed node and child, and then free the node itself.
    In cases 1 and 3 because no copy is done we need to chek if the removed is the begin or root and update according to it.
    In cases 2 and 3 we need to check the end stab                                                                              */
TreeIter TreeRemove(Tree* _tree, TreeIter _iter)
{
    Node* node      = 0;
    Node* movedNode = 0;
    Node* nextNode  = 0;
    Node* prevNode  = 0;

    assert(_iter);
    assert( ((Node*)_iter)->m_data != (void*)0xdeadbeef );        /*  not stab end */

    node = ((Node*)_iter);
    if(!node->m_smaller && (!node->m_bigger || node->m_bigger == &(_tree->m_end) )) /*  If there isn't childs (or no left child but has the stab end)  */
    {
        if(node == _tree->m_root)                                             /*  And now tree is empty   */
        {
            _tree->m_root  = 0;
            _tree->m_begin = &(_tree->m_end);
            _tree->m_end.m_parent = 0;

            return (TreeIter)&(_tree->m_end);
        }

        nextNode = node->m_parent;
        if(node == _tree->m_begin)
        {
            _tree->m_begin = nextNode;                          /*  Because it has no child if it's begin, it has to be that parent is the next  */
        }

        if(node->m_bigger == &(_tree->m_end))                   /*  Update the end stab */
        {
            _tree->m_end.m_parent = nextNode;
        }

        UpdateParentAndFreeNode(node, node->m_bigger);          /*  If it's NULL puts it, if end puts it in right place of parent   */
    }
    else
    {
        nextNode = NodeNext(node);
        if(node->m_bigger && node->m_bigger != &(_tree->m_end) && node->m_smaller)  /*  Node has 2 childs                                   */
        {
            node->m_data = nextNode->m_data;                                    /*  Copy data of next to removed node                       */
            if(nextNode->m_bigger)                                              /*  If nextNode has bigger side */
            {
                nextNode->m_bigger->m_parent = nextNode->m_parent;              /*  Attach the bigger with parent   */
            }
            UpdateParentAndFreeNode(nextNode, nextNode->m_bigger);              /*  Update next parent and free it.                         */
            nextNode = node;                                                    /*  Now will return the node itself (that is now the next)  */
        }
        else                                                                    /*  Node has one child                                      */
        {
            if(node->m_smaller)                                                 /*  If it has smaller child, the "moved" node is smaller    */
            {
                movedNode = node->m_smaller;
            }
            else
            {
                movedNode = node->m_bigger;
            }

            movedNode->m_parent = node->m_parent;                               /*  Update the parent of node   */

            if(node == _tree->m_begin)
            {
                _tree->m_begin = nextNode;
            }

            if(node->m_bigger == &(_tree->m_end))                               /*  Update the end stab         */
            {
                prevNode = NodePrev(node);
                _tree->m_end.m_parent = prevNode;
                prevNode->m_bigger = &(_tree->m_end);
            }

            if(node != _tree->m_root)                                           /*  If node is not the root update the parent of node       */
            {
                UpdateParentAndFreeNode(node, movedNode);
            }
            else                                                                /*  Update the tree->root to the moving node instead of removed one.    */
            {
                _tree->m_root = movedNode;
                free(node);
            }
        }
    }

    return (TreeIter)nextNode;
}

/***************************************************************************************************************/
/*********************************************    Tree_UTEST    ************************************************/
/***************************************************************************************************************/
#ifdef TREE_UTEST
#define IS_SUCCESS(X) !X?"SUCCESS":"FAILURE"   /*  Macro to print on regression tests       */
#define IF_FAIL(X) if(X){printf("FAIL IN %s TEST, IN LINE %d\n",#X,__LINE__); return 1;}
/*******************    Forward Declerations    ******************/
int TreeRegression_Utest();
int TreeCreate_Utest();
int TreeInsert_Utest();
/*****************************************************************/

int TreeRegression_Utest()
{
    printf("TreeCreate_Utest: %s\n\n", IS_SUCCESS(TreeCreate_Utest()));
    printf("TreeInsert_Utest: %s\n\n", IS_SUCCESS(TreeInsert_Utest()));

    return 0;
}

int main()
{
    TreeRegression_Utest();

    return 0;
}

int LessFunction(void* _a , void* _b)
{
    return *(int*)_a < *(int*)_b ;
}

int TreeCreate_Utest()
{
    Tree* tree = TreeNew(LessFunction);
    int i1 = 5;
    int i2 = 7;

    IF_FAIL(!tree->m_less((void*)&i1 , (void*)&i2))
    IF_FAIL(tree->m_less((void*)&i2 , (void*)&i1))
    IF_FAIL(tree->m_less((void*)&i1 , (void*)&i1))

    return 0;
}

int TreeInsert_Utest()
{
    Tree* tree = TreeNew(LessFunction);
    int i1 = 5;
    int i2 = 7;
    int i3 = 3;
    int i4 = 2;

    IF_FAIL(!TreeIsEmpty(tree))

    TreeInsert(tree, &i1);
    IF_FAIL(TreeIsEmpty(tree))
    TreeInsert(tree, &i2);
    TreeInsert(tree, &i3);
    TreeInsert(tree, &i4);

    printf("%d\n", *(int*)(tree->m_root->m_data));
    printf("%d\n", *(int*)(tree->m_root->m_bigger->m_data));
    printf("%d\n", *(int*)(tree->m_root->m_smaller->m_data));
    printf("%d\n", *(int*)(tree->m_root->m_smaller->m_smaller->m_data));

    return 0;
}


#endif   /* TREE_UTEST  */
